package com.example.validatestudy.demos.algorithm.sort;

import java.util.Arrays;

/**
 * @param
 * @version v1
 * @auther WANGZHENFANG004
 * @summary 归并排序
 * @since 2024 06 24 19 26
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] arr = {30,40,60,10,20,50};
        arr = mergeSort(arr);
        for(int i=0;i<arr.length;i++){
            System.out.println(arr[i]);
        }
    }

    public static int[] mergeSort(int[] arr){
        int length = arr.length;
        if(length<2) {
            return arr;
        }
        int middle = length/2;
        int[] a = Arrays.copyOfRange(arr,0,middle);
        int[] b = Arrays.copyOfRange(arr,middle,length);
        a = mergeSort(a);
        b = mergeSort(b);
        return merge(a,b);
    }

    public static int[] merge(int[] a,int[] b){
        int ai=0,bi=0,length=a.length+b.length;
        int[] arr = new int[length];
        for (int i = 0; i < length; i++) {
            if(ai<a.length &&bi<b.length){
                if( a[ai]<b[bi]){
                    arr[i] = a[ai];
                    ai++;
                }else{
                    arr[i] = b[bi];
                    bi++;
                }
            }else if(ai<a.length){
                arr[i] = a[ai];
                ai++;
            }else if(bi<b.length){
                arr[i] = b[bi];
                bi++;
            }
        }
        return arr;
    }
}
